// 设计一个支持在平均 时间复杂度 O(1) 下， 执行以下操作的数据结构。
// 注意: 该数据结构允许出现重复元素；且所有操作时间复杂度要求均为O1

// insert(val)：向集合中插入元素 val，返回布尔值判断该元素是否重复
// remove(val)：当 val 存在时，从集合中移除一个 val，返回布尔值判断删除是否成功
// getRandom：从现有集合中随机获取一个元素。每个元素被返回的概率应该与其在集合中的数量呈线性相关。


// 暴露数据结构
class RandomizedCollection {
    protected hashMap: Map<number, Set<number>>;// 内部哈希集合
    protected list: number[];// 内部栈
    // 构造函数
    constructor() {
        this.hashMap = new Map();
        this.list = [];
    }
    // O1 插入元素方法
    insert(val: number): boolean {
        const indexSet = this.hashMap.has(val) ? this.hashMap.get(val)! : new Set<number>();
        indexSet.add(this.list.length);// 添加最新的下标索引
        this.list.push(val);
        this.hashMap.set(val, indexSet);
        return indexSet.size === 1;
    }
    // O1 随机访问方法
    getRandom(): number {
        return this.list[Math.floor(Math.random() * this.list.length)];
    }
    // O1 随机删除方法
    remove(val: number): boolean {
        const indexSet = this.hashMap.get(val);
        if (indexSet == null) {
            return false;
        }
        let deletIndex: number = -1;
        // 取出第一个哈希集下标，只循环第一个元素
        for (let index of indexSet.values()) {
            deletIndex = index;
            indexSet.delete(deletIndex);// 删除对应的哈希集数值
            break;
        }
        // 最后一个元素与要删除的元素交换
        let lastNum: number = this.list[this.list.length - 1];
        this.list[deletIndex] = lastNum;
        // 最后一个元素的下标集合更新
        this.hashMap.get(lastNum)!.delete(this.list.length - 1);
        // 这里要注意！！要考虑删除的元素和最后一个元素是一个的情况
        if (deletIndex < this.list.length - 1) {
            this.hashMap.get(lastNum)!.add(deletIndex);
        }
        // 考虑哈希集为空的情况
        if (indexSet.size === 0) {
            this.hashMap.delete(val);
        }
        // 终于可以删除元素了
        this.list.pop();
        return true;
    }
}




// 这道题目是一道难度较大的程序设计题
// 复杂的地方主要存在于怎么用O1的时间复杂度删除元素？
// O1的插入和随机访问这两个API用数组其实就相当好实现了
// 现在来思考如何用O1的时间复杂度实现删除指定元素
// 我们可以发现，其实列表中元素的顺序是无关紧要的，只要它们正确地存在于列表中即可。
// 因此，在删除元素时，我们可以将被删的元素与列表中最后一个元素交换位置，
// 随后便可以在 O(1) 时间内，利用数组的pop去除该元素
// 这样我们就必须精确的知道每个元素对应的下标有哪些（毕竟元素也有可能重复）
// 这需要我们额外维护数值在列表中每一次出现的下标集合为HashSet
// 这是需要一个数据结构哈希表，key值为数组中出现过的值，value值则为对应的下标哈希集合
// 在删除时，我们找出删除元素在hashset出现的第一个下标，
// 并将这个下表对应的元素与最后一个元素进行交换
// 但这里会有比较细节的处理
// 首先，交换之后，被交换元素原本的下标集合是需要更新的
// 其次，要删除交换元素可能本身就是最后一个元素，这种情况下是不需要更新下标集合的
// 之后，原本的删除元素可能被删除了之后它对应的哈希集合为空了，这种时候需要更新维护的哈希表
// 经过这些考虑才可以正常的出栈最后一个元素


